package study;
public class code_sugerChild {

    // 相邻的两个小盆友得分一样怎么分糖果都没问题
    // 得分不一样，分数多的小盆友得到的糖果数比分数少的小盆友多
    // 求最少需要多少糖果
    // arr 头尾相邻

    //解题思路
    // 先找到 arr 中最小的数    
    public static int findMin (int[] arr){
        int min= -1;
        for (int i = 1; i < arr.length-1; i++) {
            
            if (arr[i-1]>= arr[i] && arr[i] <= arr[i+1]) {
                min= arr[i];
            }
        }
        return min;
    }
    
    public static int suger(int[] arr,int start,int cur,int suger){
        // 环形边界 
        // last = cur - 1 往前到0  cur = n-1 
        // next = cur + 1 往后到n  cur = 0   
        int last = cur - 1;
        int next = cur + 1;
        if (cur-1 == 0) {
            last = arr.length -1;
        }
        else if (cur+1 == arr.length) {
            next = 0;
        }

        if(last == start){
            return 0;
        }

        if (arr[last] > arr[cur]) {
            suger += suger(arr,start,last,suger+1);
        }
        if (arr[cur] < arr[next]) {
            suger += suger(arr,start,last,suger+1);
        }

        return suger;
    }
    
    public static void main(String[] args) {
        int[] arr = {1,23,4,5,63,37,7,2,7,33,66,7,557,7,7,78,8,66,6,6,6,0,1};
        System.out.println("最少糖果："+suger(arr,findMin(arr),findMin(arr),1));
    }
}
